package com.github.algorithm.sort;

/**
 * 通用的一些排序算法
 * @author Stephen
 * @date 2020/6/8 14:13
 */
public class CommonSort {


    //插入排序
    public static void insertSort(int[] array) {
        int i, j, temp;
        for (i=1; i<array.length; i++) {
            temp = array[i];
            for (j=i-1; j>=0 && temp < array[j]; j--)
                array[j+1] = array[j];
            array[j+1] = temp;
        }
    }

    //希尔排序
    public static void shellSort(int[] array) {
        int len = array.length;
        for (int delta = len/2; delta > 0; delta /= 2)
            for (int i = delta; i < len; i++)
                modInsertSort(array, delta, i);
    }

    //改进后的插入
    public static void modInsertSort(int[] array, int delta, int i) {
        int j;
        int temp = array[i];
        for (j = i-delta; j >= 0 && temp < array[j]; j -= delta)
            array[j+delta] = array[j];
        array[j+delta] = temp;
    }

    //优化后的希尔排序
    public static void modShellSort(int[] array) {


    }

    //quick sort
    public static void quickSort(int[] array, int left, int right) {
        int pivot = 0;
        if (left < right) {
            pivot = partition(array, left, right);
            quickSort(array, left, pivot-1);
            quickSort(array, pivot+1, right);
        }
    }
    public static int partition(int[] array, int left, int right) {
        int key = array[left]; //左边的作为key
        while (left < right) {
            while (left < right && key <= array[right]) right--;
            array[left] = array[right];
            while (left < right && key >= array[left]) left++;
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }


    /**
     * 桶式排序
     */
    public static void bucketSort(int[] array, int min, int max) {

        int[] temp = new int[array.length];
        int[] buckets = new int[max-min];


    }
}
